package warm100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class canFinish_207 {
    /**
     *  BFS广度优先搜索
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 初始化一个数组来记录每个课程的入度（即有多少先修课程）
        int[] indegrees = new int[numCourses];
        // 使用一个列表的列表来表示邻接表，用于存储每个课程的后继课程
        List<List<Integer>> adjacency = new ArrayList<>();

        // 为每个课程创建一个空的邻接列表
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());

        // 遍历先修课程数组，填充入度数组和邻接表
        for(int[] cp : prerequisites) {
            // cp[0]是课程编号，cp[1]是先修课程的编号
            // 增加课程cp[0]的入度,   即修读cp[0]需要先修读课程数量
            indegrees[cp[0]]++;
            // 在先修课程cp[1]的邻接列表中添加课程cp[0]  即cp[1] :  .......->cp[0]
            adjacency.get(cp[1]).add(cp[0]);
        }

        // 初始化一个队列（存储每个轮次所有入度为0的节点，用于下次遍历），用于进行广度优先搜索（BFS）
        Queue<Integer> queue = new LinkedList<>();

        // 将所有入度为0的课程加入队列，这些课程没有先修课程，可以立即开始学习
        for(int i = 0; i < numCourses; i++)
            if(indegrees[i] == 0) queue.add(i);

        // 使用广度优先搜索进行拓扑排序
        while(!queue.isEmpty()) {
            // 从队列中取出一个入度为0的课程
            int pre = queue.poll();
            // 减少课程总数，因为已经完成了一个课程
            numCourses--;
            // 遍历当前课程的邻接列表，即所有依赖于它的课程
            for(int cur : adjacency.get(pre)) {
                // 减少依赖课程的入度，因为先修课程已经完成
                if(--indegrees[cur] == 0) {
                    // 如果依赖课程的入度变为0，将其加入队列
                    queue.add(cur);
                }
            }
        }

        // 如果所有课程都被成功完成，则课程总数应该为0
        return numCourses == 0;
    }

    /**
     * DFS深度优先搜索
     */
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();

        // 为每个课程创建一个空的邻接列表
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());

//        记住这三个标志位对应的状态
//        未被 DFS 访问：i == 0；
//        已被其他节点启动的 DFS 访问：i == -1；
//        已被当前节点启动的 DFS 访问：i == 1，当一次DFS出现两次相同节点则有环。
        int[] flags = new int[numCourses];

        //邻接表的创建
        for(int[] cp : prerequisites)
            adjacency.get(cp[1]).add(cp[0]);
        for(int i = 0; i < numCourses; i++)
            if(!dfs(adjacency, flags, i)) return false;
        return true;
    }

    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        //当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 2 次访问，即 课程安排图有环 ，直接返回 False。
        if(flags[i] == 1) return false;
        //当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 True。
        if(flags[i] == -1) return true;
        //将当前访问节点 i 对应 flag[i] 置 1，即标记其被本轮 DFS 访问过；
        flags[i] = 1;

        for(Integer j : adjacency.get(i))
            if(!dfs(adjacency, flags, j)) return false;

        //当前节点开始的所有DFS并没有发现环，则将当前节点 flag 置为 −1 并返回 True。
        flags[i] = -1;
        return true;
    }

}

